package hot100;

import org.junit.Test;

public class MaxProduct {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int[] dpMax = new int[n];//dp[i]代表以nums[i]为结尾的乘积最大的子数组
        int[] dpMin = new int[n];//dp[i]代表以nums[i]为结尾的乘积最小的子数组

        for (int i = 0; i < n; i++) {
            dpMax[i] = nums[i];
            dpMin[i] = nums[i];
        }

        int res = dpMax[0];
        for (int i = 1; i < n; i++) {
            if (nums[i] < 0) {
                dpMax[i] = Math.max(dpMax[i],dpMin[i - 1] * nums[i]);
                dpMin[i] = Math.min(dpMin[i],dpMax[i - 1] * nums[i]);
            } else {
                dpMax[i] = Math.max(dpMax[i],dpMax[i - 1] * nums[i]);
                dpMin[i] = Math.min(dpMin[i],dpMin[i - 1] * nums[i]);
            }
            res = Math.max(res,dpMax[i]);
        }

        return res;
    }

    @Test
    public void test() {
        int[] nums = new int[]{-1,-2,-9,-6};
        System.out.println(maxProduct(nums));
    }
}
